package com.demo.example.hot100;

import java.util.ArrayList;
import java.util.List;

public class GenerateBracket {
    public static void main(String[] args) {
        List<String> res=generateParenthesis(3);
        for(String s:res){
            System.out.println(s);
        }
    }
    //n对括号，总共2n个位置，每个位置有两种可能
    public static List<String> generateParenthesis(int n) {
        List<String> res=new ArrayList<>();
        generateAll(new char[2*n],0,res);
        return res;
    }
    public static void generateAll(char[] current,int pos,List<String> result){
        if(pos==current.length){
            if(isValid(current)){
                result.add(new String(current));
            }
        }else{
            current[pos]='(';
            generateAll(current,pos+1,result);
            current[pos]=')';
            generateAll(current,pos+1,result);
        }
    }
    public static boolean isValid(char[] current){
        int balance=0;
        for(int i=0;i<current.length;i++){
            if(current[i]=='('){
                balance++;
            }else{
                balance--;
            }
            if(balance<0){
                return false;
            }
        }
        return balance==0;
    }
}
